TNotes.leetcode

Appearance

0338. 比特位计数【简单】

0338. 比特位计数【简单】 ​

1. 📝 题目描述 ​

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

txt
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

txt
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

  • 0 <= n <= 10^5

进阶：

  • 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
  • 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const result = new Array(n + 1)

  for (let i = 0; i <= n; i++) {
    result[i] = countOnes(i)
  }

  return result
}

// 计算一个数字二进制表示中 1 的个数
function countOnes(num) {
  let count = 0
  while (num > 0) {
    count += num & 1
    num >>= 1
  }
  return count
}
  • 时间复杂度：O(nlog⁡n)，每个数字需要 O(log⁡n) 时间计算
  • 空间复杂度：O(1)，不考虑输出数组

3. 🎯 s.2 - 动态规划 - 最低有效位 ​

js
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const result = new Array(n + 1)
  result[0] = 0

  for (let i = 1; i <= n; i++) {
    result[i] = result[i >> 1] + (i & 1)
    // i >> 1 表示去除最低位
    // result[i >> 1] 表示去掉最低位后，剩下的部分有多少个 1。（这是复用已计算好的结果）
    // (i & 1) 检查最低位是不是 1
  }

  return result
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

4. 🎯 s.3 - 动态规划 - 最低设置位（推荐） ​

js
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const result = new Array(n + 1)
  result[0] = 0 // 0 的二进制中没有 1

  for (let i = 1; i <= n; i++) {
    // i & (i - 1) 会清除 i 的最低位的 1
    // 例如：6 (110) → 6 & 5 = 4 (100)
    // 所以 i 比 i & (i - 1) 多一个 1
    result[i] = result[i & (i - 1)] + 1
  }

  return result
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

5. 🎯 s.4 - 动态规划 - 最高有效位 ​

js
/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const result = new Array(n + 1)
  result[0] = 0

  let highBit = 0
  for (let i = 1; i <= n; i++) {
    // 当 i 是 2 的幂时，更新最高有效位
    if ((i & (i - 1)) === 0) {
      highBit = i
    }
    // i 的 1 的个数 = (i - highBit) 的 1 的个数 + 1
    result[i] = result[i - highBit] + 1
  }

  return result
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

Discussions